左递归文法 | 您所在的位置:网站首页 › 文法 g[e] : e→e - t∣t t→t*f∣f › 左递归文法 |
一个文法含有下列形式的产生式之一时: 1)A→Aβ,A∈VN,β∈V* 2)A→Bβ,B→Aα,A、B∈VN,α、β∈V* 则称该文法是左递归的。 然而,一个文法是左递归时,不能采取自顶向下分析法。 消除左递归方法有: a)把直接左递归改写为右递归: 设有文法产生式:A→Aβ|γ。其中β非空,γ不以A打头。 可写为:A→γA' A'→βA'|ε 一般情况下,假定关于A的产生式是: A→Aα1| Aα2 |… |Aαm|β1|β2 |…|βn 其中,αi(1≤i≤m)均不为空,βj(1≤j≤n)均不以A打头。 则消除直接左递归后改写为: A→ β1A'| β2 A' |…| βnA' A'→ α1A' | α2A' |…| αmA' |ε 例4.12:有文法G(E): E→E +T |T T→T*F | F F→i| (E) 消除该文法的直接左递归。 解:按转换规则,可得: E→TE' E'→+TE'|ε T→FT ' T'→*FT'|ε F→i| (E) b)消除间接左递归: 对于间接左递归的消除需要先将间接左递归变为直接左递归,然后再按a)清除左递归。 例4.13:以文法G6为例消除左递归: (1)A→aB (2)A→Bb (3)B→Ac (4)B→d 解:用产生式(1),(2)的右部代替产生式(3)中的非终结A得到左部为B的产生式: (1)B→aBc (2)B→Bbc (3)B→d 消除左递归后得到: B→aBcB' |dB' B'→bcB' |ε 再把原来其余的产生式A→aB,A→Bb加入,最终得到等价文法为: (1) A→aB (2) A→Bb (3) B→(aBc|d)B' (4) B'→bcB'|ε c)消除文法中一切左递归的算法 设非终结符按某种规则排序为A1,A2,…,An。 For i﹕=1 to n do begin For j﹕=1 to i-1 do begin 若Aj的所有产生式为: Aj →δ1| δ2 | … | δn 替换形如Ai → Aj γ的产生式为: Ai →δ1γ |δ2γ | … |δnγ end 消除Ai中的一切直接左递归 end |
今日新闻 |
推荐新闻 |
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 |